
namespace AlgorithmMergeSort {
    // show debug log
    const isDebug: boolean = true;

    // 辅助函数：顺序合并两个数组
    function merge(left: number[], right: number[]): number[] {
        let result: number[] = [];
        while (left.length > 0 && right.length > 0) {
            if (left[0] < right[0]) {
                //@ts-ignore
                result.push(left.shift());
            } else {
                //@ts-ignore
                result.push(right.shift());
            }
        }
        result = result.concat(left, right);
        if (isDebug)
            console.log(`新数组长度${result.length}，合并排序后的数组：\n`, JSON.stringify(result));
        return result;
    }
    // 递归, 自上而下的方法
    function mergeSort(arr: number[]): number[] {
        const len: number = arr ? arr.length : 0;
        if (len <= 1) return arr;
        const middle = len >> 1;
        const left = arr.slice(0, middle);
        const right = arr.slice(middle);
        if (isDebug)
            console.log(`数组长度${len}, 中位数${middle}，拆分后的两个数组：\n左：`, JSON.stringify(left), " 右：", JSON.stringify(right));
        return merge(mergeSort(left), mergeSort(right));
    }

    function main() {
        const ary: number[] = [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70];
        if (isDebug)
            console.log(`数组长度${ary.length}，排序前数组：\n`, JSON.stringify(ary));
        mergeSort(ary);
    }
    main();
}